package com.longge;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-06-05 00:20
 */
public class BalanceBST {
    private List<Integer> arr = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        dfs(root);
        int size = arr.size();
        return buildBST(arr, 0, size - 1);
    }

    private TreeNode buildBST(List<Integer> arr, int start, int end) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode treeNode = new TreeNode(arr.get(mid));
        treeNode.left = buildBST(arr, start, mid - 1);
        treeNode.right = buildBST(arr, mid + 1, end);
        return treeNode;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        arr.add(root.val);
        dfs(root.right);
    }
}
